#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int f[ 3001 ][ 3001 ], a[ 3001 ], d[ 3001 ];
short s[ 3001 ][ 3001 ];
int n, m;

int sum( int x, int y )
{
    int mid = ( x + y ) / 2, ret = 0, t;
    if ( x > y ) return 0;
    if ( mid > x )
    {
        t = 0;
        if ( x ) t = d[ x - 1 ];
        ret += ( mid - x ) * a[ mid ] - ( d[ mid - 1 ] - t );
    }
    if ( y > mid )
        ret += d[ y ] - d[ mid ] - ( y - mid ) * a[ mid ];
    return ret;
}

void init( )
{
    int i;
    scanf("%d%d", &n, &m);
    for ( i = 0; i < n; i++ )
        scanf("%d", &a[ i ]);
    sort( a, a + n );
    d[ 0 ] = a[ 0 ];
    for ( i = 1; i < n; i++ )
        d[ i ] = d[ i - 1 ] + a[ i ];
    for ( i = 0; i < n; i++ )
    {
        s[ i ][ 1 ] = 0;
        f[ i ][ 1 ] = sum( 0, i );        
    }
}

void work( )
{
    int i, j, k;
    for ( i = 2; i <= m; i++ )
    {
        s[ n ][ i ] = n - 1;
        for ( j = n - 1; j >= i - 1; j-- )
        {
            f[ j ][ i ] = 100000000;
            for ( k = s[ j ][ i - 1 ]; k <= s[ j + 1 ][ i ]; k++ )
            {
                if ( f[ j ][ i ] > f[ k ][ i - 1 ] + sum( k + 1, j ) )
                {
                    f[ j ][ i ] = f[ k ][ i - 1 ] + sum( k + 1, j );
                    s[ j ][ i ] = k;
                }
            }
        }
    }
    printf("%d\n", f[ n - 1 ][ m ]);
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
    }
    return 0;
}
